/**
 * 冒泡排序算法的JavaScript实现
 * 相比原始Python版本进行了多项性能优化
 */

/**
 * 基础冒泡排序实现
 * @param {Array} arr - 需要排序的数组
 * @returns {Array} - 排序后的数组
 */
function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

/**
 * 优化版冒泡排序实现
 * 优化点：
 * 1. 添加标志位，当一轮比较没有发生交换时，说明数组已经有序，提前退出
 * 2. 记录每轮最后一次交换的位置，下一轮只需要比较到该位置
 * 3. 使用解构赋值简化交换操作
 * 
 * @param {Array} arr - 需要排序的数组
 * @returns {Array} - 排序后的数组
 */
function optimizedBubbleSort(arr) {
    const n = arr.length;
    let swapped;
    let lastSwapIndex = n - 1;
    
    do {
        swapped = false;
        let currentSwapIndex = 0;
        
        for (let j = 0; j < lastSwapIndex; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
                currentSwapIndex = j;
            }
        }
        
        // 更新最后交换的位置
        lastSwapIndex = currentSwapIndex;
        
    } while (swapped);
    
    return arr;
}

/**
 * 双向冒泡排序（鸡尾酒排序）
 * 优化点：
 * 1. 双向比较，同时从前往后和从后往前进行冒泡
 * 2. 减少排序轮数，提高效率
 * 
 * @param {Array} arr - 需要排序的数组
 * @returns {Array} - 排序后的数组
 */
function cocktailSort(arr) {
    let swapped;
    let start = 0;
    let end = arr.length - 1;
    
    do {
        swapped = false;
        
        // 从左到右冒泡
        for (let i = start; i < end; i++) {
            if (arr[i] > arr[i + 1]) {
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                swapped = true;
            }
        }
        
        // 如果没有交换，说明数组已经有序
        if (!swapped) break;
        
        swapped = false;
        end--;
        
        // 从右到左冒泡
        for (let i = end - 1; i >= start; i--) {
            if (arr[i] > arr[i + 1]) {
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                swapped = true;
            }
        }
        
        start++;
        
    } while (swapped);
    
    return arr;
}

// 测试代码
function testSorting() {
    const testArrays = [
        [64, 34, 25, 12, 22, 11, 90],
        [5, 2, 8, 12, 1, 3],
        [1, 2, 3, 4, 5], // 已排序
        [5, 4, 3, 2, 1], // 逆序
        [1], // 单元素
        []   // 空数组
    ];
    
    console.log("原始冒泡排序测试:");
    testArrays.forEach(arr => {
        const arrCopy = [...arr];
        console.log(`原始数组: ${arrCopy}`);
        console.log(`排序结果: ${bubbleSort(arrCopy)}`);
        console.log("---");
    });
    
    console.log("\n优化版冒泡排序测试:");
    testArrays.forEach(arr => {
        const arrCopy = [...arr];
        console.log(`原始数组: ${arrCopy}`);
        console.log(`排序结果: ${optimizedBubbleSort(arrCopy)}`);
        console.log("---");
    });
    
    console.log("\n双向冒泡排序测试:");
    testArrays.forEach(arr => {
        const arrCopy = [...arr];
        console.log(`原始数组: ${arrCopy}`);
        console.log(`排序结果: ${cocktailSort(arrCopy)}`);
        console.log("---");
    });
}

// 执行测试
testSorting();

// 导出函数，方便其他模块使用
module.exports = {
    bubbleSort,
    optimizedBubbleSort,
    cocktailSort
}; 